<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>♻️编码技巧 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/60.ab782775.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/55.d8f9004b.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/61.6dd12daf.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/63.6f8a4742.js"><link rel="prefetch" href="/assets/js/64.6f8bb1fa.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/66.360c2d2b.js"><link rel="prefetch" href="/assets/js/67.26f84d32.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/9.3813842d.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>♻️编码技巧</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#目录" class="sidebar-link">目录</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#📑-目录" class="sidebar-link">📑 目录</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_01-双指针" class="sidebar-link">01.双指针</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_1-1-综述：双指针的常见技巧" class="sidebar-link">1.1.综述：双指针的常见技巧</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_1-2-low和fast指针『快慢指针』" class="sidebar-link">1.2.low和fast指针『快慢指针』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_1-3-左右指针" class="sidebar-link">1.3.左右指针</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_1-4-滑动窗口『模板』" class="sidebar-link">1.4.滑动窗口『模板』</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_02-递归⭐️" class="sidebar-link">02.递归⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_2-1-递归套路『重要』⭐️" class="sidebar-link">2.1.递归套路『重要』⭐️</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_03-将『栈和递归』转换得炉火纯青⭐️" class="sidebar-link">03.将『栈和递归』转换得炉火纯青⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_3-1-递归转栈『万能模板』⭐️" class="sidebar-link">3.1.递归转栈『万能模板』⭐️</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_3-2-递归解法" class="sidebar-link">3.2.递归解法</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_3-3-栈解法" class="sidebar-link">3.3.栈解法</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_04-迭代" class="sidebar-link">04.迭代</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_05-空间换时间" class="sidebar-link">05.空间换时间</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_06-前缀-中缀-后缀表达式⭐️" class="sidebar-link">06.前缀/中缀/后缀表达式⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_6-1-中缀表达式转换为后缀表达式" class="sidebar-link">6.1.中缀表达式转换为后缀表达式</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_6-2-计算后缀表达式" class="sidebar-link">6.2.计算后缀表达式</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/SkillLibrary/Part01.%E7%BC%96%E7%A0%81%E6%8A%80%E5%B7%A7.html#_6-3-启发性的方法" class="sidebar-link">6.3.启发性的方法</a></li></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="♻️编码技巧"><a href="#♻️编码技巧" class="header-anchor">#</a> ♻️编码技巧</h1> <h2 id="目录"><a href="#目录" class="header-anchor">#</a> 目录</h2> <ul><li>⭐️一、双指针『应对-数组』</li> <li>✡️二、递归『应对-链表-树』</li> <li>🍀三、将『栈和递归』转换得炉火纯青</li> <li>✏️四、迭代</li> <li>☁️五、空间换时间之打表、记忆化（前、后缀等）</li> <li>💫六、计算中缀表达式</li></ul> <h2 id="📑-目录"><a href="#📑-目录" class="header-anchor">#</a> 📑 目录</h2> <p>[TOC]</p> <h2 id="_01-双指针"><a href="#_01-双指针" class="header-anchor">#</a> 01.双指针</h2> <ul><li>有的书上叫“尺取法”</li></ul> <h3 id="_1-1-综述：双指针的常见技巧"><a href="#_1-1-综述：双指针的常见技巧" class="header-anchor">#</a> 1.1.综述：双指针的常见技巧</h3> <ul><li>快慢指针（fast和low）</li> <li>左右指针（left和right）</li> <li>滑动窗口</li></ul> <h3 id="_1-2-low和fast指针『快慢指针』"><a href="#_1-2-low和fast指针『快慢指针』" class="header-anchor">#</a> 1.2.low和fast指针『快慢指针』</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//框架开始</span>
ListNode <span class="token operator">*</span> low<span class="token operator">=</span>pHead<span class="token punctuation">;</span>
ListNode <span class="token operator">*</span> fast<span class="token operator">=</span>pHead<span class="token punctuation">;</span>

<span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>fast<span class="token operator">-&gt;</span>next <span class="token operator">&amp;&amp;</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>fast<span class="token operator">-&gt;</span>next<span class="token operator">-&gt;</span>next <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token comment">//记得一定要先走</span>
	low<span class="token operator">=</span>low<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
	fast<span class="token operator">=</span>fast<span class="token operator">-&gt;</span>next<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
<span class="token comment">//框架结束</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> low<span class="token operator">==</span>fast <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        low<span class="token operator">=</span>pHead<span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> low<span class="token operator">!=</span>fast <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            low<span class="token operator">=</span>low<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
            fast<span class="token operator">=</span>fast<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> fast<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br></div></div><h3 id="_1-3-左右指针"><a href="#_1-3-左右指针" class="header-anchor">#</a> 1.3.左右指针</h3> <ul><li>二分查找用到了</li> <li>判断是否回文</li></ul> <h3 id="_1-4-滑动窗口『模板』"><a href="#_1-4-滑动窗口『模板』" class="header-anchor">#</a> 1.4.滑动窗口『模板』</h3> <ul><li>框架</li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>string str;
int Left=0,Right=0,Len=str.size();
while( Right&lt;Len )
{
	//右侧强制更新的,下面必须保留，否则++Right之后会更新
    char CurChar=s[Right];
    WindowsHash[ CurChar ]++;
    ++Right;
    //右侧非强制更新的，本部分不需要更新
            

	//『何时使得窗口不符合条件』，使得左侧需要更新？收缩？
	//用的while循环收缩，毕竟可能要收缩很多次
	while( how to shrink)
	{
        char c=s[Left];
        WindowsHash[c]--;
        ++Left;
        //其他的
	}
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br></div></div><h4 id="例题1-26-删除有序数组中的重复项"><a href="#例题1-26-删除有序数组中的重复项" class="header-anchor">#</a> 例题1-<a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/" target="_blank" rel="noopener noreferrer">26. 删除有序数组中的重复项<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h4> <ul><li>严格来说是“左右指针”，不全是“滑动窗口”</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">int</span> <span class="token function">removeDuplicates</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
 
        <span class="token keyword">int</span> Left<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> Right<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">//“滑动窗口”在本题中的改进点1</span>
        <span class="token keyword">int</span> Len<span class="token operator">=</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">while</span><span class="token punctuation">(</span> Right<span class="token operator">&lt;</span>Len <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//改进点2</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">[</span>Right<span class="token punctuation">]</span><span class="token operator">==</span>nums<span class="token punctuation">[</span>Left<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                nums<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">+</span>Right<span class="token punctuation">,</span> nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">+</span>Right<span class="token operator">+</span><span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">--</span>Len<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">[</span>Right<span class="token punctuation">]</span><span class="token operator">!=</span>nums<span class="token punctuation">[</span>Left<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">++</span>Left<span class="token punctuation">;</span>
                <span class="token operator">++</span>Right<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>


        <span class="token keyword">return</span> Len<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br></div></div><h4 id="例题2-3-无重复字符的最长子串"><a href="#例题2-3-无重复字符的最长子串" class="header-anchor">#</a> 例题2-<a href="https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/" target="_blank" rel="noopener noreferrer">3. 无重复字符的最长子串<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">int</span> <span class="token function">lengthOfLongestSubstring</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> res<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        unordered_map<span class="token operator">&lt;</span><span class="token keyword">char</span><span class="token punctuation">,</span><span class="token keyword">int</span><span class="token operator">&gt;</span> WindowsHash<span class="token punctuation">;</span>
        <span class="token keyword">int</span> Left<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>Right<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> Len<span class="token operator">=</span>s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">while</span><span class="token punctuation">(</span> Right<span class="token operator">&lt;</span>Len <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//右侧强制更新的,下面必须保留，否则++Right之后会更新</span>
            <span class="token keyword">char</span> CurChar<span class="token operator">=</span>s<span class="token punctuation">[</span>Right<span class="token punctuation">]</span><span class="token punctuation">;</span>
            WindowsHash<span class="token punctuation">[</span> CurChar <span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token operator">++</span>Right<span class="token punctuation">;</span>
            <span class="token comment">//右侧非强制更新的，本部分不需要更新</span>
            

            <span class="token comment">//『何时使得窗口不符合条件』，使得左侧需要更新？收缩？</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> WindowsHash<span class="token punctuation">[</span> CurChar <span class="token punctuation">]</span> <span class="token operator">&gt;</span><span class="token number">1</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token keyword">char</span> c<span class="token operator">=</span>s<span class="token punctuation">[</span>Left<span class="token punctuation">]</span><span class="token punctuation">;</span>
                WindowsHash<span class="token punctuation">[</span>c<span class="token punctuation">]</span><span class="token operator">--</span><span class="token punctuation">;</span>
                <span class="token operator">++</span>Left<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            res<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> res<span class="token punctuation">,</span> Right<span class="token operator">-</span>Left <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> res<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br></div></div><h2 id="_02-递归⭐️"><a href="#_02-递归⭐️" class="header-anchor">#</a> 02.递归⭐️</h2> <h3 id="_2-1-递归套路『重要』⭐️"><a href="#_2-1-递归套路『重要』⭐️" class="header-anchor">#</a> 2.1.递归套路『重要』⭐️</h3> <ul><li>来自《算法基础与在线实践》</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> n<span class="token punctuation">;</span>
<span class="token comment">//表示，begin借助help杆子，到end上面去，这次的目标是移动n个元素</span>
<span class="token keyword">void</span> <span class="token function">hanota</span><span class="token punctuation">(</span><span class="token keyword">char</span> begin<span class="token punctuation">,</span> <span class="token keyword">char</span> help<span class="token punctuation">,</span> <span class="token keyword">char</span> end<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> n<span class="token operator">&lt;</span><span class="token number">1</span> <span class="token punctuation">)</span>	<span class="token keyword">return</span> <span class="token punctuation">;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">1</span><span class="token operator">==</span>n <span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%c-&gt;%c\n&quot;</span><span class="token punctuation">,</span> begin<span class="token punctuation">,</span> end<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">return</span> <span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token comment">//这个递归，是观察小部分的调用获得的idea</span>
	<span class="token function">hanota</span><span class="token punctuation">(</span> begin<span class="token punctuation">,</span> end<span class="token punctuation">,</span> help<span class="token punctuation">,</span> n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%c-&gt;%c\n&quot;</span><span class="token punctuation">,</span> begin<span class="token punctuation">,</span> end<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">hanota</span><span class="token punctuation">(</span> help<span class="token punctuation">,</span> begin<span class="token punctuation">,</span> end<span class="token punctuation">,</span> n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">~</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span> <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token function">hanota</span><span class="token punctuation">(</span> <span class="token string">'A'</span><span class="token punctuation">,</span> <span class="token string">'B'</span><span class="token punctuation">,</span> <span class="token string">'C'</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br></div></div><h2 id="_03-将『栈和递归』转换得炉火纯青⭐️"><a href="#_03-将『栈和递归』转换得炉火纯青⭐️" class="header-anchor">#</a> 03.将『栈和递归』转换得炉火纯青⭐️</h2> <ul><li>二叉树的<a href="https://leetcode-cn.com/problems/binary-tree-preorder-traversal/submissions/" target="_blank" rel="noopener noreferrer">前序遍历<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h3 id="_3-1-递归转栈『万能模板』⭐️"><a href="#_3-1-递归转栈『万能模板』⭐️" class="header-anchor">#</a> 3.1.递归转栈『万能模板』⭐️</h3> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>0、使用结构体量的成员变量或指针变，抽象原先解决问题的『递归函数』的形式参数
1、设置 『问题栈』并且，画出和书上差不多的解决问题，栈变化表
2、初始化『第1个问题』
    st.push( root );
3、用while循环，模拟栈
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><ul><li>郭炜，《<a href="https://book.douban.com/subject/27023415/" target="_blank" rel="noopener noreferrer">算法基础与在线实践<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>》P74，递归和栈的解法</li> <li>率辉，2020版<a href="https://book.douban.com/subject/30777887/" target="_blank" rel="noopener noreferrer">数据结构高分笔记<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>（第8版）</li></ul> <h3 id="_3-2-递归解法"><a href="#_3-2-递归解法" class="header-anchor">#</a> 3.2.递归解法</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */</span>

vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ret<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">trave</span><span class="token punctuation">(</span> TreeNode <span class="token operator">*</span> root <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> root<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">trave</span><span class="token punctuation">(</span> root<span class="token operator">-&gt;</span>left <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">trave</span><span class="token punctuation">(</span> root<span class="token operator">-&gt;</span>right <span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">preorderTraversal</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> root<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        
        ret<span class="token punctuation">.</span><span class="token function">clear</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">trave</span><span class="token punctuation">(</span> root <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br></div></div><h3 id="_3-3-栈解法"><a href="#_3-3-栈解法" class="header-anchor">#</a> 3.3.栈解法</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */</span>

vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ret<span class="token punctuation">;</span>
stack<span class="token operator">&lt;</span> TreeNode <span class="token operator">*</span> <span class="token operator">&gt;</span> st<span class="token punctuation">;</span><span class="token comment">//第1步，设置 『问题栈』</span>
<span class="token keyword">void</span> <span class="token function">trave</span><span class="token punctuation">(</span> TreeNode <span class="token operator">*</span> root <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token comment">//第2步，初始化『第1个问题』</span>
    st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> root <span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token comment">//第3步，用while循环，模拟栈</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span>st<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        TreeNode <span class="token operator">*</span> top<span class="token operator">=</span>st<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        st<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>top <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            st<span class="token punctuation">.</span><span class="token function">push</span> <span class="token punctuation">(</span> top<span class="token operator">-&gt;</span>right <span class="token punctuation">)</span><span class="token punctuation">;</span>
            st<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> top<span class="token operator">-&gt;</span>left <span class="token punctuation">)</span><span class="token punctuation">;</span>
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> top<span class="token operator">-&gt;</span>val <span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//着手解决问题</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

<span class="token punctuation">}</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">preorderTraversal</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> root<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        
        ret<span class="token punctuation">.</span><span class="token function">clear</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span>st<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            st<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token function">trave</span><span class="token punctuation">(</span> root <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br></div></div><h2 id="_04-迭代"><a href="#_04-迭代" class="header-anchor">#</a> 04.迭代</h2> <ul><li>链表遍历</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span>  <span class="token function">MyReverse</span><span class="token punctuation">(</span> ListNode <span class="token operator">*</span> root <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">!=</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        cout<span class="token operator">&lt;&lt;</span> <span class="token punctuation">(</span>root<span class="token operator">-&gt;</span>val<span class="token punctuation">)</span> <span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
        root <span class="token operator">=</span> root<span class="token operator">-&gt;</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br></div></div><h2 id="_05-空间换时间"><a href="#_05-空间换时间" class="header-anchor">#</a> 05.空间换时间</h2> <ul><li>比如，求素数</li></ul> <h2 id="_06-前缀-中缀-后缀表达式⭐️"><a href="#_06-前缀-中缀-后缀表达式⭐️" class="header-anchor">#</a> 06.前缀/中缀/后缀表达式⭐️</h2> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">struct</span> <span class="token class-name">node</span>
<span class="token punctuation">{</span>
    <span class="token keyword">double</span> num<span class="token punctuation">;</span> <span class="token comment">//操作数字</span>
    <span class="token keyword">char</span> op<span class="token punctuation">;</span>    <span class="token comment">//操作符</span>
    <span class="token keyword">bool</span> flag<span class="token punctuation">;</span>  <span class="token comment">//true表示操作数，false表示操作符</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>

string str<span class="token punctuation">;</span>
stack<span class="token operator">&lt;</span>node<span class="token operator">&gt;</span> s<span class="token punctuation">;</span><span class="token comment">//操作符栈</span>
queue<span class="token operator">&lt;</span>node<span class="token operator">&gt;</span> q<span class="token punctuation">;</span><span class="token comment">//后缀表达式序列</span>
map<span class="token operator">&lt;</span><span class="token keyword">char</span><span class="token punctuation">,</span><span class="token keyword">int</span><span class="token operator">&gt;</span> op<span class="token punctuation">;</span>

<span class="token comment">//将中缀表达式转换为后缀表达式</span>
<span class="token keyword">void</span> <span class="token function">Change</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">Cal</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    op<span class="token punctuation">[</span><span class="token string">'+'</span><span class="token punctuation">]</span><span class="token operator">=</span>op<span class="token punctuation">[</span><span class="token string">'-'</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>  <span class="token comment">//设定操作符的优先级</span>
    op<span class="token punctuation">[</span><span class="token string">'*'</span><span class="token punctuation">]</span><span class="token operator">=</span>op<span class="token punctuation">[</span><span class="token string">'/'</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token function">getline</span><span class="token punctuation">(</span>cin<span class="token punctuation">,</span>str<span class="token punctuation">)</span><span class="token punctuation">,</span> str<span class="token operator">!=</span><span class="token string">&quot;0&quot;</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span> string<span class="token operator">::</span>iterator it<span class="token operator">=</span>str<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> it<span class="token operator">!=</span>str<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> it<span class="token operator">--</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//将表达式中的空格删掉</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token string">' '</span><span class="token operator">==</span><span class="token punctuation">(</span><span class="token operator">*</span>it<span class="token punctuation">)</span> <span class="token punctuation">)</span> str<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span>it<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span> 
        <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span>s<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            s<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>    <span class="token comment">//初始化栈</span>
        <span class="token punctuation">}</span>

        <span class="token comment">//将中缀表达式转换为后缀表达式</span>
        <span class="token function">Change</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">//计算后缀表达式</span>
        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%.2f\n&quot;</span><span class="token punctuation">,</span> <span class="token function">Cal</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br></div></div><h3 id="_6-1-中缀表达式转换为后缀表达式"><a href="#_6-1-中缀表达式转换为后缀表达式" class="header-anchor">#</a> 6.1.中缀表达式转换为后缀表达式</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>
<span class="token keyword">void</span> <span class="token function">Change</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">double</span> num<span class="token punctuation">;</span>
    node temp<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span> <span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>str<span class="token punctuation">.</span><span class="token function">length</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token function">isdigt</span><span class="token punctuation">(</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            temp<span class="token punctuation">.</span>flag<span class="token operator">=</span><span class="token boolean">true</span><span class="token punctuation">;</span><span class="token comment">//标记是数字</span>
            temp<span class="token punctuation">.</span>num<span class="token operator">=</span>str<span class="token punctuation">[</span>i<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">'0'</span><span class="token punctuation">;</span><span class="token comment">//记录这个操作数的的1个数位</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> i<span class="token operator">&lt;</span>str<span class="token punctuation">.</span><span class="token function">length</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> <span class="token function">isdigt</span><span class="token punctuation">(</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//更新该操作数『常见编程技巧』</span>
                temp<span class="token punctuation">.</span>num<span class="token operator">=</span>temp<span class="token punctuation">.</span>num<span class="token operator">*</span><span class="token number">10</span><span class="token operator">+</span><span class="token punctuation">(</span> str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">'0'</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">++</span>i<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token comment">//将这个操作数压入后缀表达式的队列</span>
            q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//如果是操作符</span>
            temp<span class="token punctuation">.</span>flag<span class="token operator">=</span><span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token comment">//只要操作符的栈顶元素比该操作符优先级高</span>
            <span class="token comment">//就把操作符栈顶元素弹出到后缀表达式的队列中</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> s<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> op<span class="token punctuation">[</span> str<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">]</span><span class="token operator">&lt;=</span>op<span class="token punctuation">[</span> s<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>op <span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> s<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
                s<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            temp<span class="token punctuation">.</span>op<span class="token operator">=</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            s<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>   <span class="token comment">//把该操作符压入操作符栈中</span>
            <span class="token operator">++</span>i<span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token comment">//#end inner if</span>

        <span class="token comment">//如果操作符栈中还有操作符，就把它弹出到后缀表达式中</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span>s<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> s<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            s<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        
    <span class="token punctuation">}</span><span class="token comment">//#end for</span>

<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br></div></div><h3 id="_6-2-计算后缀表达式"><a href="#_6-2-计算后缀表达式" class="header-anchor">#</a> 6.2.计算后缀表达式</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">Cal</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">double</span> temp1<span class="token punctuation">,</span>temp2<span class="token punctuation">;</span>
    node cur<span class="token punctuation">,</span>temp<span class="token punctuation">;</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span>q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token comment">//cur记录队首元素</span>
        cur<span class="token operator">=</span>q<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        q<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//如果是操作数，直接压入栈</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token boolean">true</span><span class="token operator">==</span>cur<span class="token punctuation">.</span>flag <span class="token punctuation">)</span> 
        <span class="token punctuation">{</span>
            s<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>cur<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//如果是操作符，号</span>
            temp2<span class="token operator">=</span>s<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>num<span class="token punctuation">;</span>  <span class="token comment">//弹出第2操作数</span>
            s<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            temp1<span class="token operator">=</span>s<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>num<span class="token punctuation">;</span>  <span class="token comment">//弹出第1操作数</span>
            s<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token comment">//临时记录操作数</span>
            temp<span class="token punctuation">.</span>flag<span class="token operator">=</span><span class="token boolean">true</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token string">'+'</span><span class="token operator">==</span>cur<span class="token punctuation">.</span>op <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                temp<span class="token punctuation">.</span>num<span class="token operator">=</span>temp1<span class="token operator">+</span>temp2<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token string">'-'</span><span class="token operator">==</span>cur<span class="token punctuation">.</span>op <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                temp<span class="token punctuation">.</span>num<span class="token operator">=</span>temp1<span class="token operator">-</span>temp2<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token string">'*'</span><span class="token operator">==</span>cur<span class="token punctuation">.</span>op <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                temp<span class="token punctuation">.</span>num<span class="token operator">=</span>temp1<span class="token operator">*</span>temp2<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
                temp<span class="token punctuation">.</span>num<span class="token operator">=</span>temp1<span class="token operator">/</span>temp2<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//将该操作数压入栈</span>
            s<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span> temp <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token comment">//#end inner if &amp; else</span>


    <span class="token punctuation">}</span><span class="token comment">//#end while</span>

    <span class="token comment">//栈顶元素就是后缀表达式的值</span>
    <span class="token keyword">return</span> s<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>num<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br></div></div><h3 id="_6-3-启发性的方法"><a href="#_6-3-启发性的方法" class="header-anchor">#</a> 6.3.启发性的方法</h3> <ul><li>NC137 <a href="https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4?tpId=188&&tqId=38548&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking" target="_blank" rel="noopener noreferrer">表达式求值<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>请写一个整数计算器，支持加减乘三种运算和括号。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><ul><li>参考思路：labuladong</li></ul></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/60.ab782775.js" defer></script>
  </body>
</html>
